/*
 * BitTools.h
 *
 *  Created on: 03/08/2012
 *      Author: marcio
 */

#ifndef BITTOOLS_H_
#define BITTOOLS_H_

#include <stdlib.h>

/*!
 * \def hum_u a word with 32 bits, all set to 1
 * \def fum_l a word with 64 bits all set to 1
 */
#define hum_u  0xFFFFFFFF
#define hum_l  0xFFFFFFFFFFFFFFF

/*! \fn inline_ceillog(long n, int b)
 * \brief Determine the ceil of the logarithmic of the specified value in the specified basis.
 *
 * The algorithm is the following: the specified value is successively divided by the specified basis until 1 is obtained.
 * The number of times the specified gives the floor of the logarithmic. If the remainder of some these divisions is
 * different from 0, then the floor is incremented by 1 before it is returned.
 *
 * \param n the value.
 * \param b the logarithmic (in basis 2) of the basis.
 *
 * \return the ceil of the logarithmic of the specified value in the specified basis.
 *
 */
static inline int inline_ceillog(long n, int b) {
	long c = 0;
	int l = 0;
	while (n >= (1LL << b)) {
		c |= (n & ~(-1 << b));
		n >>= b;
		l++;
	}
	if (c)
		l++;
	return l;
}

/*! \fn builtinCounter(T i)
 * \brief Builtin function to determine the number of bits 1 in the word i.
 *
 * Builtin functions are functions provided to the compiler and depended on the
 * architecture of the computer to work properly. This kind of function is usually
 * implemented in hardware level. In order to use this function you have to verify
 * if the compiler has support to that and if not rewrite this function.
 *
 * More documentation about builtin functions can be viewed in
 *
 * \sa http://en.wikipedia.org/wiki/C_standard_library
 * \sa http://gcc.gnu.org/onlinedocs/gcc/Other-Builtins.html
 *
 * \param i the word.
 * \tparam the type of the word.
 *
 * \return the number of bits 1 in i.
 *
 */
template <typename T>
static inline int builtinCounter(T i);

template <>
inline int builtinCounter(long long i) {
	return __builtin_popcountll(i);
}

template <>
inline int builtinCounter(long i) {
	return __builtin_popcountl(i);
}

template <>
inline int builtinCounter(int i) {
	return __builtin_popcount(i);
}

/*! \fn builtinLeast(T i)
 * \brief Builtin function to determine the least significant bit 1 in the word i.
 *
 * Builtin functions are functions provided to the compiler and depended on the
 * architecture of the computer to work properly. This kind of function is usually
 * implemented in hardware level. In order to use this function you have to verify
 * if the compiler has support to that and if not rewrite this function.
 *
 * More documentation about builtin functions can be viewed in
 *
 * \sa http://en.wikipedia.org/wiki/C_standard_library
 * \sa http://gcc.gnu.org/onlinedocs/gcc/Other-Builtins.html
 *
 * \param i the word.
 * \tparam the type of the word.
 *
 * \return the least significant bit 1 in i, if the word has o bit 1 it will return -1.
 *
 */
template <typename T>
static inline int builtinLeast(T i);

template <>
inline int builtinLeast(long long i) {
	return __builtin_ffsll(i)-1;
}

template <>
inline int builtinLeast(long i) {
	return __builtin_ffsl(i)-1;
}

template <>
inline int builtinLeast(int i) {
	return __builtin_ffs(i)-1;
}

/*! \fn builtinMost(T i)
 * \brief Builtin function to determine the most significant bit 1 in the word i
 *
 * Builtin functions are functions provided to the compiler and depended on the
 * architecture of the computer to work properly. This kind of function is usually
 * implemented in hardware level. In order to use this function you have to verify
 * if the compiler has support to that and if not rewrite this function.
 *
 * More documentation about builtin functions can be viewed in
 *
 * \sa http://en.wikipedia.org/wiki/C_standard_library
 * \sa http://gcc.gnu.org/onlinedocs/gcc/Other-Builtins.html
 *
 * \param i the value.
 * \tparam the type of the word.
 *
 * \return the most significant bit 1 in i, if the word has no bit 1 it will return -1.
 *
 */
template <typename T>
static inline int builtinMost(T i);

template <>
inline int builtinMost(long long i) {
	return (sizeof(long long) << 3)-__builtin_clzll(i)-1;
}

template <>
inline int builtinMost(long i) {
	return (sizeof(long) << 3)-__builtin_clzl(i)-1;
}

template <>
inline int builtinMost(int i) {
	return (sizeof(int) << 3)-__builtin_clz(i)-1;
}


static const int posmasksimp[32] =
{
		hum_u , hum_u << 1, hum_u << 2, hum_u << 3, hum_u << 4, hum_u << 5, hum_u << 6, hum_u << 7,
		hum_u << 8, hum_u << 9, hum_u << 10, hum_u << 11, hum_u << 12, hum_u << 13, hum_u << 14, hum_u << 15,
		hum_u << 16, hum_u << 17, hum_u << 18, hum_u << 19, hum_u << 20, hum_u << 21, hum_u << 22, hum_u << 23,
		hum_u << 24, hum_u << 25, hum_u << 26, hum_u << 27, hum_u << 28, hum_u << 29, hum_u << 30, hum_u << 31
};

static const long long posmasklsimp[64] =
{
		hum_l , hum_l << 1, hum_l << 2, hum_l << 3, hum_l << 4, hum_l << 5, hum_l << 6, hum_l << 7,
		hum_l << 8, hum_l << 9, hum_l << 10, hum_l << 11, hum_l << 12, hum_l << 13, hum_l << 14, hum_l << 15,
		hum_l << 16, hum_l << 17, hum_l << 18, hum_l << 19, hum_l << 20, hum_l << 21, hum_l << 22, hum_l << 23,
		hum_l << 24, hum_l << 25, hum_l << 26, hum_l << 27, hum_l << 28, hum_l << 29, hum_l << 30, hum_l << 31,
		hum_l << 32 , hum_l << 33, hum_l << 34, hum_l << 35, hum_l << 36, hum_l << 37, hum_l << 38, hum_l << 39,
		hum_l << 40, hum_l << 41, hum_l << 42, hum_l << 43, hum_l << 44, hum_l << 45, hum_l << 46, hum_l << 47,
		hum_l << 48, hum_l << 49, hum_l << 50, hum_l << 51, hum_l << 52, hum_l << 53, hum_l << 54, hum_l << 55,
		hum_l << 56, hum_l << 57, hum_l << 58, hum_l << 59, hum_l << 60, hum_l << 61, hum_l << 62, hum_l << 63
};



static const unsigned int __mask[17] =
{
		0xFFFF,
		0xFFFE, 0xFFFC, 0xFFF8, 0xFFF0,
		0xFFE0, 0xFFC0, 0xFF80, 0xFF00,
		0xFE00, 0xFC00, 0xF800, 0xF000,
		0xE000, 0xC000, 0x8000, 0x0000
};

static const unsigned long __maskl[33] =
{
		0xFFFFFFFF,
		0xFFFFFFFE, 0xFFFFFFFC, 0xFFFFFFF8, 0xFFFFFFF0,
		0xFFFFFFE0, 0xFFFFFFC0, 0xFFFFFF80, 0xFFFFFF00,
		0xFFFFFE00, 0xFFFFFC00, 0xFFFFF800, 0xFFFFF000,
		0xFFFFE000, 0xFFFFC000, 0xFFFF8000, 0xFFFF0000,
		0xFFFE0000, 0xFFFC0000, 0xFFF80000, 0xFFF00000,
		0xFFE00000, 0xFFC00000, 0xFF800000, 0xFF000000,
		0xFE000000, 0xFC000000, 0xF8000000, 0xF0000000,
		0xE0000000, 0xC0000000, 0x80000000, 0x00000000
};

static const unsigned long long __maskll[65] =
{
		0xFFFFFFFFFFFFFFFF,
		0xFFFFFFFFFFFFFFFE, 0xFFFFFFFFFFFFFFFC, 0xFFFFFFFFFFFFFFF8, 0xFFFFFFFFFFFFFFF0,
		0xFFFFFFFFFFFFFFE0, 0xFFFFFFFFFFFFFFC0, 0xFFFFFFFFFFFFFF80, 0xFFFFFFFFFFFFFF00,
		0xFFFFFFFFFFFFFE00, 0xFFFFFFFFFFFFFC00, 0xFFFFFFFFFFFFF800, 0xFFFFFFFFFFFFF000,
		0xFFFFFFFFFFFFE000, 0xFFFFFFFFFFFFC000, 0xFFFFFFFFFFFF8000, 0xFFFFFFFFFFFF0000,
		0xFFFFFFFFFFFE0000, 0xFFFFFFFFFFFC0000, 0xFFFFFFFFFFF80000, 0xFFFFFFFFFFF00000,
		0xFFFFFFFFFFE00000, 0xFFFFFFFFFFC00000, 0xFFFFFFFFFF800000, 0xFFFFFFFFFF000000,
		0xFFFFFFFFFE000000, 0xFFFFFFFFFC000000, 0xFFFFFFFFF8000000, 0xFFFFFFFFF0000000,
		0xFFFFFFFFE0000000, 0xFFFFFFFFC0000000, 0xFFFFFFFF80000000, 0xFFFFFFFF00000000,
		0xFFFFFFFE00000000, 0xFFFFFFFC00000000, 0xFFFFFFF800000000, 0xFFFFFFF000000000,
		0xFFFFFFE000000000, 0xFFFFFFC000000000, 0xFFFFFF8000000000, 0xFFFFFF0000000000,
		0xFFFFFE0000000000, 0xFFFFFC0000000000, 0xFFFFF80000000000, 0xFFFFF00000000000,
		0xFFFFE00000000000, 0xFFFFC00000000000, 0xFFFF800000000000, 0xFFFF000000000000,
		0xFFFE000000000000, 0xFFFC000000000000, 0xFFF8000000000000, 0xFFF0000000000000,
		0xFFE0000000000000, 0xFFC0000000000000, 0xFF80000000000000, 0xFF00000000000000,
		0xFE00000000000000, 0xFC00000000000000, 0xF800000000000000, 0xF000000000000000,
		0xE000000000000000, 0xC000000000000000, 0x8000000000000000, 0x0000000000000000
};

static const unsigned long __nnodesh[8] =
{
		0x00000000,
		0x00000001, 0x00000021, 0x00000421,	0x00008421,
		0x00108421,	0x02108421, 0x42108421
};


#endif /* BITTOOLS_H_ */
